import org.junit.Test;

import java.util.*;

public class Solution1331 {
    /**
     * 给你一个整数数组 arr ，请你将数组中的每个元素替换为它们排序后的序号。
     *
     * 序号代表了一个元素有多大。序号编号的规则如下：
     *
     * 序号从 1 开始编号。
     * 一个元素越大，那么序号越大。如果两个元素相等，那么它们的序号相同。
     * 每个数字的序号都应该尽可能地小。
     *
     */
    public int[] arrayRankTransform(int[] arr) {
        if (arr.length == 0) return new int[0];
        Queue<Integer> queue = new PriorityQueue<>();
        queue.add(arr[0]);
        for (int i = 1; i < arr.length; i++) {
            queue.add(arr[i]);
        }
        Map<Integer, Integer> map = new HashMap<>();
        int i = 1;
        Integer pre = null;
        while (!queue.isEmpty()){
            Integer poll = queue.poll();
            if (!poll.equals(pre)){
                map.put(poll, i++);
            }
            pre = poll;
        }
        for (int j = 0; j < arr.length; j++) {
            arr[j] = map.get(arr[j]);
        }
        return arr;
    }

    @Test
    public void test(){
        arrayRankTransform(new int[]{37,12,28,9,100,56,80,5,12});
    }
}
